package com.mgq.algorithm.unionfind;

/**
 * 岛问题
 * 岛问题可以使用并查集来并行计算.来达到加速
 */
public class CountIsland {
    public static int maxAreaOfIsland(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        //res是用来统计次数的
        int res = 0;
        //max是用来计算最大面积的
        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //依次检查,发现是1,就感染
                if (grid[i][j] == 1) {
                    res++;
                    max = Math.max(infect(grid, i, j, N, M), max);
                }
            }
        }
        return max;
    }

    /**
     * infect过程,将矩阵中上下左右为1的全部变为2
     *
     * @param grid 二维数组
     * @param i    当前所在的行
     * @param j    当前所在的列
     * @param N    有多少行
     * @param M    有多少列
     */
    public static int infect(int[][] grid, int i, int j, int N, int M) {
        int count = 0;
        //因为infect会将1改为2,所以这个函数最终会结束
        //i>=N 之所以等于N,是因为感染会感染下一行,所以最后一行不用再检查
        if (i < 0 || i >= N || j < 0 || j >= M || grid[i][j] != 1) {
            return 0;
        }
        //改为2
        grid[i][j] = 2;
        count++;
        count += infect(grid, i, j - 1, N, M);
        count += infect(grid, i, j + 1, N, M);
        count += infect(grid, i - 1, j, N, M);
        count += infect(grid, i + 1, j, N, M);
        return count;
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{{1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}};
        System.out.println(maxAreaOfIsland(grid));
    }
}
